1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to techniques for facilitating efficient implementations of mutual exclusion mechanisms.
2. Description of the Related Art
The mutual exclusion problem has a long history. Beginning with Dijkstra's publication of Dekker's first correct mutual exclusion lock in 1965 (E. Dijkstra, Solution to a Problem in Concurrent Programming Control, Communications of the ACM, 8(9):569 (1965)), and continuing through to the present time, mutual exclusion locks have been the focus of hundreds if not thousands of research papers and other technical writings. Because the problem is so pervasive, it ranks among the most well-known in all of computer science.
As formally specified, the mutual exclusion problem arises in a domain wherein each participating process executes, in strict cyclic order, program regions labeled remainder, acquire, critical section, and release. A solution to the mutual exclusion problem then can be defined in the form of code for the acquire( ) and release( ) operations. These operations guarantee that once a process successfully completes an acquire( ) operation, no other process will complete an acquire( ) operation before the first process invokes a release( ) operation. Solutions to the mutual exclusion problem are often referred to as locks.
An important advance in the study of lock performance is due to Lamport. See L. Lamport, A Fast Mutual Exclusion Algorithm, ACM Transactions on Computer Systems, 5(1):1-11 (1987). In Lamport's fast mutual exclusion algorithm, a fast path guarantees that the lock and unlock operations complete in time independent of the number of potential contending processes in the important case where a single process contends for the lock in isolation. Locks that share this property are called fast locks, and most important locks used in production software are fast locks. While Lamport's algorithm was the first to use only load and store operations in a fast path, it depends on sequential consistency and therefore its advantages do not extend to modern shared memory architectures that support weaker memory models.
Within the category of fast locks, we have focused on identifying particularly important sub-cases as well as on how to optimize for them. One such sub-case that we believe to be particularly important in multithreaded computing systems, such as those that build-upon JAVA™ technology or .NET common language runtime (CLR) technology, is the case where a single process (or thread) repeatedly acquires and releases a lock, but other processes (or threads) rarely, if ever, access that lock. Such cases typically arise in actual program execution sequences because historically, the overhead of locking has been such that system designers have gone to great lengths (in the design of data structures and algorithms) to avoid synchronization overheads wherever possible. In such designs, locks are acquired by a dominant process primarily to provide safety in the case where another process needs to share access to the data; however, these cases are very rare by design. Java and all Java-based marks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
Another important sub-case relates to adaptivity to variations in execution environments, particularly as programmers seek to achieve platform-independent synchronization of concurrent processes (and/or threads). Such goals encourage the use of structures and techniques that map well to a variety of execution environments, including both single-threaded and multi-threaded execution environments.
What is needed are mutual exclusion techniques whose performance is enhanced or optimized for actual program execution sequences in which a dominant process (or thread) repeatedly acquires and releases a lock, but other processes (or threads) rarely, if ever, access the lock. What is also needed are mutual exclusion techniques that impose limited or minimal overhead when included in program code that, during a particular execution thereof, executes as a single-threaded computation or in an execution environment where hazards of concurrent execution are otherwise obviated.